package com.yuren.codecrushlearn.Q5200;

/**
 * Created with Intellij IDEA.
 * Description:
 * 支持动态扩容的HashMap
 * @author 10204
 * @date 2025-04-27 00:00
 */
public class Q5215 {
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final int INITIAL_CAPACITY = 1 << 3;
    static final float LOAD_FACTOR = 0.75f;

    Node[] nodes;
    int size;
    int threshold;

    public Q5215() {
        this.nodes = new Node[INITIAL_CAPACITY];
        this.size = 0;
        this.threshold = (int) (nodes.length * LOAD_FACTOR);
    }

    public void put(int key, int value) {
        int idx = hash(key) & (capacity() - 1);
        Node now = nodes[idx], tmp = now;
        if (tmp != null) {
            Node prev = null;
            while (tmp != null) {
                if (tmp.key == key) {
                    tmp.value = value;
                    return;
                }
                prev = tmp;
                tmp = tmp.next;
            }
            tmp = prev;
        }

        Node node = new Node(key, value);
        if (tmp != null) {
            tmp.next = node;
        } else {
            nodes[idx] = node;
        }

        if (++size > threshold)
            resize();
    }

    public int get(int key) {
        int idx = hash(key) & (capacity() - 1);
        Node now = nodes[idx];

        if (now != null) {
            if (now.key == key) {
                return now.value;
            } else {
                while (now != null) {
                    if (now.key == key) {
                        return now.value;
                    }
                    now = now.next;
                }
            }
        }

        return -1;
    }

    public void remove(int key) {
        int idx = hash(key) & (capacity() - 1);
        Node now = nodes[idx];

        if (now != null) {
            Node prev = null;
            while (now != null) {
                if (now.key == key) {
                    if (prev != null) {
                        prev.next = now.next;
                    } else {
                        nodes[idx] = now.next;
                    }
                    now.next = null;
                    size--;
                    return;
                }
                prev = now;
                now = now.next;
            }
        }
    }

    int capacity() {
        return nodes.length;
    }

    private int hash(int key) {
        int hash = Integer.hashCode(key);
        hash ^= (hash >>> 16);
        return hash;
    }

    final Node[] resize() {
        Node[] oldNodes = nodes;
        int oldCapacity = capacity();

        if (oldCapacity == MAXIMUM_CAPACITY) {
            return oldNodes;
        }

        int newCapacity = oldCapacity << 1;
        int newThreshold = (int) (newCapacity * LOAD_FACTOR);
        Node[] newNodes = new Node[newCapacity];

        for (int i = 0; i < oldCapacity; i++) {
            Node node = oldNodes[i];
            if (node != null) {
                int newIndex = hash(node.key) & (newCapacity - 1);
                if (newNodes[newIndex] == null) {
                    newNodes[newIndex] = node;
                } else {
                    Node curr = newNodes[newIndex];
                    while (curr.next != null) {
                        curr = curr.next;
                    }
                    curr.next = node;
                }
            }
            oldNodes[i] = null;
        }

        threshold = newThreshold;
        nodes = newNodes;
        return newNodes;
    }

    static class Node {
        int key, value;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}
